前缀和
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。子数组是数组中元素的连续非空序列。O(nlogn)
这道题的关键在于如何以O(1)的复杂度发现和为k的子数组个数, 重点在于子数组一定连续, 连续的一段区间的和可以用前缀以O(1)求得, 问题在于如何知道这样的数的个数.
对于运算到第i处的前缀per[i], 前面可以和其相减得到k的per, 有或没有, 有多少都是问题, 那么就可以进行per值的存储, 要把其数量也一并记录, 那么用map就可以了.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
int subarraySum(vector<int>& nums, int k){
vector<int> pre(nums.size() + 10);
map<int, int> mp;
mp[0] = 1;
int ans = 0;
for(int i = 0; i < nums.size(); i ++ )
{
pre[i] = nums[i];
if(i != 0) pre[i] += pre[i - 1];
if(mp.count(pre[i] - k)) ans += mp[pre[i] - k];
mp[pre[i]]++;
}
return ans;
}
};
|
滑动窗口
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。
标准例题, 深入理解的关键在于这里的滑动窗口是一个固定值, 就要把控制窗口的变量和队列的操作分清楚.
队列 : 本题中要维护的是一个单减队列, 就是为了保证队头一定是最大值, 为了实现这个目的, 只要新元素比队尾元素小就要弹出队尾元素, 直到遇到大于等于的.
窗口 : 窗口的移动在遍历中实现, 可以想到只要i - k >= 0, 每次向后移动一格就一定会离开一个加入一个.
问题的关键在于队列会提前弹出部分元素, 所以队列的实际大小和原窗口是匹配不上的, 也就是说, 即使i - k >= 0, 如果队头还没有到应该弹出的时间, 就不能弹出, 而到了应该弹出的时候就必须弹出.
问题就转化成了 : 随着窗口的移动, 如何确定队头所在的元素是否离开了区域?
其实只需要对比当前要离开的元素是否和队头元素值相等就行了, 因为如果是其他值, 就一定是还没轮到队头, 不然不可能会出现这个队头存在的情况.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
deque<int> dq;
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> ret;
int n = nums.size();
for(int i = 0; i < n; i ++ )
{
while(dq.size() && dq.back() < nums[i]) dq.pop_back();
dq.push_back(nums[i]);
if(i - k >= 0 && dq.front() == nums[i - k]) dq.pop_front();
if(i - k + 1 >= 0) ret.push_back(dq.front());
}
return ret;
}
};
|
合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
例题, 核心在于区间需要排序, 我们需要在左端点从小到达排列的前提下去分析才能有效.
剩下的其实就是控制住当前区间的左右端点[nl, nr], 对新加入的区间[l, r]进行分析 :
- 加入l > nr, 那么区间根本不相交, 这是一个新的区间, 于是将大权转移.
- l <= nr, 那么区间相交, 接着就是看右端点还需不需要更新 :
- r > nr, 新的右边界更大, 右边界主权转移.
- r <= nr, 说明这个新区间完全被包含在原区间中, 不做调整.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
vector<vector<int>> ret;
vector<vector<int>>& a = intervals;
sort(a.begin(), a.end());
int nl = -1, nr = -1;
for(int i = 0; i < a.size(); i ++ )
{
int l = a[i][0], r = a[i][1];
if(l > nr)
{
if(nr != -1)
{
vector<int> v = {nl, nr};
ret.push_back(v);
}
nl = l, nr = r;
}
else
{
if(nr < r) nr = r;
}
}
vector<int> v = {nl, nr};
bool flag = false;
for(auto e : ret)
{
if(e[0] == nl)
{
flag = true;
break;
}
}
if(!flag) ret.push_back(v);
return ret;
}
};
|